#include <iostream>
#include <string>
#include "HashMap.h"

// 最大堆
void MaxHeap(std::string &s, int n, int i)
{
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    int max = i;
    if(left < n && s[left] > s[max])
        max = left;
    if(right < n && s[right] > s[max])
        max = right;

    if(max != i)
    {
        std::swap(s[i], s[max]);
        MaxHeap(s, n, max);
    }
}

// 堆排
void Sort(std::string &s)
{
    int n = s.size();
    for(int i = n / 2 - 1; i >= 0; i--)
    {
        MaxHeap(s, n, i);
    }
    for(int i = n - 1; i >= 0; i--)
    {
        std::swap(s[0], s[i]);
        MaxHeap(s, i, 0);
    }
}

int main()
{
#if 0
    HashMap m(100);

    m.Insert("zhangsan", 100);
    m.Insert("lisi", 90);
    m.Insert("wangwu", 80);

    m.show();

    // std::cout<<*m.Get("wangwu")<<std::endl;

    m["zhangsan"] = 100;
    m["lisi"] = 90;
    m["wangwu"] = 80;
    m["zhaoliu"] = 95;
    m["houmingqiang"] = 95;

    // m.Remove("houmingqiang");
    m.show();
#endif

#if 1
    // 字母异位词（eat ate）
    HashMap m(100);

    // std::string s = "zhangsan";
    // Sort(s);
    // std::cout<<s<<std::endl;

    // 按照字母异位词分组
    std::string s[] = {"eat", "ate", "tan", "tea", "nat", "bat"};
    for(int i = 0; i < 6; i++)
    {
        // 不能直接对原字符串排序
        std::string temp = s[i];
        Sort(temp);
        m.Insert(temp, s[i]);
    }

    m.showByGroup();
#endif

    return 0;
}